//给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。 
//
// 换句话说，s1 的排列之一是 s2 的 子串 。 
//
// 
//
// 示例 1： 
//
// 
//输入：s1 = "ab" s2 = "eidbaooo"
//输出：true
//解释：s2 包含 s1 的排列之一 ("ba").
// 
//
// 示例 2： 
//
// 
//输入：s1= "ab" s2 = "eidboaoo"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s1.length, s2.length <= 104 
// s1 和 s2 仅包含小写字母 
// 
// Related Topics 哈希表 双指针 字符串 滑动窗口 
// 👍 396 👎 0

package leetcode.editor.cn;

/**
 * Java：字符串的排列
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P567_PermutationInString {
    public static void main(String[] args) {
        Solution solution = new P567_PermutationInString().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean checkInclusion(String s1, String s2) {
            return indexOfAim(s2, s1) == -1 ? false : true;
        }

        public int indexOfAim(String str, String aim) {
            if (str == null || aim == null || str.length() == 0 || aim.length() == 0) {
                return -1;
            }
            if (str.length() < aim.length()) {
                return -1;
            }
            // 初始化词频表
            int[] wf = new int[256];
            for (char c : aim.toCharArray()) {
                wf[c]++;
            }
            char[] strs = str.toCharArray();
            int l = 0, r = 0, all = aim.length();
            // 初始化窗口
            for (; r < aim.length(); r++) {
                // 当前字符个数大于0，all才减一
                if (wf[strs[r]]-- > 0) {
                    all--;
                }
            }
            // 窗口已形成，窗口开始移动
            while (r < strs.length) {
                // 判断之前的窗口是否符合
                if (all == 0) {
                    return l;
                }
                // r+1之后判断
                if (wf[strs[r++]]-- > 0) {
                    all--;
                }
                // l+1之前判断
                if (wf[strs[l++]]++ >= 0) {
                    all++;
                }
            }
            // 最后一次要判断下
            return all == 0 ? l : -1;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}